package codeTop;

/**
 * q329
 *
 * @author 雨凡
 * @version q329.java, v0.1
 * @date 2025/07/04/12:42
 */
public class q329 {
    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[matrix.length][matrix[0].length];
        int res = 0;
        for (int i = 0; i <m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] != 0) {
                    res = Math.max(res,dp[i][j]);
                }else {
                    res = Math.max(res,getLongest(matrix,dp,i,j));
                }
            }
        }
        return res;
    }

    private int getLongest(int[][] matrix, int[][] dp, int i, int j) {
        int max = 0;
        if (i > 0&&matrix[i-1][j]>matrix[i][j]) {
            if (dp[i-1][j] == 0) {
                max = Math.max(max,getLongest(matrix,dp,i-1,j));
            }else {
                max = Math.max(max,dp[i-1][j]);
            }
        }
        if (i < matrix.length-1&&matrix[i+1][j]>matrix[i][j]) {
            if (dp[i+1][j] == 0) {
                max = Math.max(max,getLongest(matrix,dp,i+1,j));
            }else {
                max = Math.max(max,dp[i+1][j]);
            }
        }
        if (j > 0&&matrix[i][j-1]>matrix[i][j]) {
            if (dp[i][j-1] == 0) {
                max = Math.max(max,getLongest(matrix,dp,i,j-1));
            }else {
                max = Math.max(max,dp[i][j-1]);
            }
        }
        if (j<matrix[0].length-1&&matrix[i][j+1]>matrix[i][j]) {
            if (dp[i][j+1] == 0) {
                max = Math.max(max,getLongest(matrix,dp,i,j+1));
            }else {
                max = Math.max(max,dp[i][j+1]);
            }
        }
        dp[i][j] = max+1;
        return dp[i][j];
    }
}
